// Fibonacci 求斐波那契（Fibonacci）数列
// https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/
type Fibonacci struct{}

// fibRec 递归法示例。效率不行，超时了。
// 这里写出来仅做一个示例
func fibRec(n int) int {

	if n < 1 {
		return 0
	}
	if n < 3 {
		return 1
	}

	return fibRec(n-1) + fibRec(n-2)
}

func (f *Fibonacci) fib(n int) int {
	a, b, sum := 0, 1, 0
	for x := 0; x < n; x++ {
		sum = (a + b) % 1000000007
		a = b
		b = sum
	}
	return a
}
// FrogWays 青蛙跳台阶问题
// https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/solution/mian-shi-ti-10-ii-qing-wa-tiao-tai-jie-wen-ti-dong/
type FrogWays struct{}
// solution 与斐波那契数列问题相似。
// 初始值不一样。f(0)为1，阶数为0时，只有一种跳法：不动。
func (f *FrogWays) solution(n int) int {
	a, b, sum := 1, 1, 0
	for x := 0; x < n; x++ {
		sum = (a + b) % 1000000007
		a = b
		b = sum
	}
	return a
}
// SpinArrayMin 旋转数组的最小数字
// https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
type SpinArrayMin struct{}

// 最简单的解法
func (s *SpinArrayMin) solution(numbers []int) int {

	for i := 0; i < len(numbers)-1; i++ {
		if numbers[i] > numbers[i+1]{
			return numbers[i+1]
		}
	}
	return numbers[0]
}
// 这个解法还慢了 23333
func (s *SpinArrayMin) solution2(numbers []int) int {
	i,j := 0,len(numbers) - 1
	for i < j {
		m := (i +j )/2
		if  numbers[m] > numbers[j] {
			i = m +1 
		} else if numbers[m ] < numbers[j] {
			j = m 
		}else {
			j--
		}
	}
	return numbers[i]
}